1786E - Monsters (hard version) - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ull unsigned LL
#define db double
#define ldb long double
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define complete_unique(x) (x).erase(unique(all(x)),(x).end());
#define fr(x) freopen(x,"r",stdin);
#define fw(x) freopen(x,"w",stdout);
#define mst(x,a) memset(x,a,sizeof(x));
#define lowbit(x) ((x) & (-(x)))
#define ex0 exit(0);
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define inf 0x3f3f3f3f
#define yes std::cout << "Yes\n"
#define no std::cout << "No\n"
//#pragma GCC optimize(2) // if CE please delete
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
const int base1 = 131;
const int base2 = 13331;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
typedef pair<int, int> hashv;
hashv operator + (hashv a, hashv b) {
	int c1 = a.fi + b.fi, c2 = a.se + b.se;
	if (c1 >= mod1) c1 -= mod1;
	if (c2 >= mod2) c2 -= mod2;
	return mp(c1, c2);
}
hashv operator - (hashv a, hashv b) {
	int c1 = a.fi - b.fi, c2 = a.se - b.se;
	if (c1 < 0) c1 = c1 + mod1;
	if (c2 < 0) c2 = c2 + mod2;
	return mp(c1, c2);
}
hashv operator * (hashv a, hashv b) {
	return mp(1ll * a.fi * b.fi % mod1, 1ll * a.second * b.second % mod2);
}
template <typename T>
inline T qpow(T a, int b, const int mod = 1e9 + 7) //quick_pow
{
	T res = 1;
	while (b)
	{
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}
LL gcd(LL a, LL b)
{
	return b == 0 ? a : gcd(b, a % b);
}
inline char gc() {
	static char buf[1000000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read()
{
	T x = 0, flag = 1;
	char c = gc();
	while (c < '0' || c > '9')
	{
		if (c == '-') flag = -1;
		c = gc();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = gc();
	}
	return x * flag;
}
template <typename T>
inline void pr(T x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) pr(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2E6 + 10;
const int M = 4e6 + 10;
int a[N];
int n, m, k;
struct {
	int l, r;
	int sum;
	int flag;
	int maxN;
}tr[M];
inline void build(int u, int l, int r)
{
	tr[u] = { l,r,-l,0,-l };
	if (l == r) return;
	int mid = l + r >> 1;
	build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	tr[u].flag = tr[u << 1].flag + tr[u << 1 | 1].flag;
	tr[u].maxN = std::max(tr[u << 1].maxN, tr[u << 1 | 1].maxN);
}
inline void modify(int u, int l, int r, int c)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].sum += (tr[u].r - tr[u].l + 1) * c;
		tr[u].maxN += c;
		tr[u].flag += c;
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if (tr[u].flag && tr[u].l != tr[u].r)
	{
		tr[u << 1].sum += (mid - tr[u << 1].l + 1) * tr[u].flag; tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - mid) * tr[u].flag;
		tr[u << 1].maxN += tr[u].flag; tr[u << 1 | 1].maxN += tr[u].flag;
		tr[u << 1].flag += tr[u].flag; tr[u << 1 | 1].flag += tr[u].flag;
		tr[u].flag = 0;
	}
	if (l <= mid) modify(u << 1, l, r, c);
	if (r > mid) modify(u << 1 | 1, l, r, c);
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	tr[u].maxN = std::max(tr[u << 1].maxN, tr[u << 1 | 1].maxN);
}
inline int queryMax(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		return tr[u].maxN;
	}
	int mid = tr[u].l + tr[u].r >> 1, res = -inf;
	if (tr[u].flag && tr[u].l != tr[u].r)
	{
		tr[u << 1].sum += (mid - tr[u << 1].l + 1) * tr[u].flag; tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - mid) * tr[u].flag;
		tr[u << 1].maxN += tr[u].flag; tr[u << 1 | 1].maxN += tr[u].flag;
		tr[u << 1].flag += tr[u].flag; tr[u << 1 | 1].flag += tr[u].flag;
		tr[u].flag = 0;
	}
	if (l <= mid) res = queryMax(u << 1, l, r);
	if (r > mid) res = std::max(res, queryMax(u << 1 | 1, l, r));
	return res;
}
int main()
{
	IOS;
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int mx = *max_element(a + 1, a + n + 1);
		build(1, 1, mx);
		LL s = 0,c = 0;
		for (int i = 1; i <= n; i++) {
			modify(1, a[i], mx, 1);
			s += a[i];
			++c;
			if (queryMax(1, 1, mx) > 0) {
				int l = 1, r = mx, mid;
				while (l < r) {
					mid = l + r >> 1;
					if (queryMax(1, 1, mid) > 0) r = mid;
					else l = mid + 1;
				}
				modify(1, l, mx, -1);
				s -= l;
				--c;
			}
			cout << s - (c * (c + 1)) / 2 << ' ';
		}
		cout << endl;
	}
	return 0;
}